package com.situ.mall.suanfa;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName Demo6
 * @Description TODO
 * @Author 周轩霆
 * @Date 2022/9/9 20:19
 **/

public class Demo6 {
    public static void main(String[] args) {
        int[] arr = {2,2,3,2,4,1,6,5,2,7,0,1,1,1,1,1,1,1};
        List<List<Integer>> lists = combinationSum(arr, 7);
        System.out.println(lists);

    }
    /*
     * @Author liuhaidong
     * @Description 该程序的思路
     * 2 2 2 2
     * 2 2 2
     * 2 2 3
     *
     * @Date 15:51 2019/9/25 0025
     **/
    static List<List<Integer>> lists = new ArrayList<>();

    //这个list存放所有数组
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (candidates == null || candidates.length == 0 || target < 0) {
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        dfs(list, candidates, target, 0);
        //第一个list存放小数组，
        return lists;
    }

    private static void dfs(List<Integer> list, int[] candidates, int target, int start) {
        //递归的终止条件
        if (target < 0) {
            return;
        }
        if (target == 0) {
            lists.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < candidates.length; i++) {
                list.add(candidates[i]);
                //*********************************************************
                //因为每个数字都可以使用无数次，所以递归还可以从当前元素开始
                //*********************************************************
                dfs(list, candidates, target - candidates[i], i);
                list.remove(list.size() - 1);
            }
        }
    }
}